package algorithms;

/**
 * 第一步：已知子节点是最大堆的条件下，维护父节点的最大堆性质；
 * 第二步：构建无序数组的最大堆，使用自底向上的方法，先把子节点维护成最大堆；
 * 第三步：组装为堆排序，把根节点，始终把即A[0]交换到A[n-1]
 */
public class 堆排序 {

    public static void main(String[] args) {
        int[] a = new int[]{4, 8, 1, 0, 2, 5, 5, 9, 7, 6, 3, 3};
//        int[] a = new int[]{4, 8, 1, 0};
        heapsort(a);
        printArr(a);
    }

    private static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    private static void heapsort(int[] a) {
        buildMaxHeap(a);
        for (int i = a.length - 1; i >= 0; i--) {
            exchange(a, 0, i);
            int heapsize = i;
            maxHeapify(a, heapsize, 0);
        }
    }

    /**
     * 根据无序数组构建最大堆，叶子节点本身是最大堆，自底向上逐级构建最大堆，
     * 那么当构建父节点时，子节点已经是最大堆，就可以利用maxHeapify函数处理。
     *
     * @param a
     */
    private static void buildMaxHeap(int[] a) {
        //找到最后一个非叶子节点，下表从0开始，如果找到负数，会在下面的for循环中截止
        int nonLeafIndex = a.length / 2 - 1;

        //从最后一个非叶子节点向前扫描
        for (int i = nonLeafIndex; i >= 0; i--) {
            maxHeapify(a, a.length, i);
        }
    }

    /**
     * 已知子节点已经是最大堆
     *
     * @param a
     * @param heapSize 这个参数的作用是限制左右节点的索引值不要超过heapSize
     * @param i
     */
    private static void maxHeapify(int[] a, int heapSize, int i) {
        int l = left(i);
        int r = right(i);

        int largest = i;
        if (l < heapSize && a[l] > i) {
            largest = l;
        }

        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }

        if (largest != i) {
            exchange(a, i, largest);
            maxHeapify(a, heapSize, largest);
        }

    }

    private static void exchange(int[] a, int i, int j) {
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;
    }

    /**
     * @param i 从0开始的索引
     * @return
     */
    private static int left(int i) {
        return 2 * i + 1;
    }

    private static int right(int i) {
        return 2 * i + 2;
    }
}
